﻿// https://leetcode.cn/problems/largest-rectangle-in-histogram/

/*



*/

#include <iostream>
#include <vector>

using namespace std;


class Solution {
public:
	// 暴力方法 N2 复杂度，会超时
    int largestRectangleArea(vector<int>& heights) {
		int len = heights.size();
		int square = 0;
		for(int i = 0; i < len; i++){
			if(i > 0 && heights[i] == heights[i - 1]){
                continue;
            }
			int left = i - 1, right = i + 1;
			int count = 1;
			while(left >= 0){
				if(heights[left] >= heights[i]){
					count++;
					left--;
				}else{
					break;
				}
			}
			while(right < len){
				if(heights[right] >= heights[i]){
					count++;
					right++;
				}else{
					break;
				}
			}
			if(heights[i] * count > square){
				square = heights[i] * count;
			}
		}
		return square;
    }
	
	// 单调递增
	/*
	0 2 1 5 6 2 3 0
	0 1 2 3 4 5 6 7
	一开始left = 0; 每次弹栈之后，left = 当前弹栈的位置的下一个位置
	顺序：  
		入栈 0 
		入栈 1 
		
		弹栈 1 1的右侧横坐标：2  左边是栈顶：0 right[1] = 2; left[1] = 0;
		入栈 2 
		
		入栈 3 
		入栈 4
		弹栈 4 4的右侧横坐标：5 【比较当前值和栈顶元素的大小】 左侧是3 right[4] = 5 left[4] = 3
		弹栈 3 3的右侧横坐标：5  right[3] = 5 left[3] = 2
		入栈 5
		入栈 6
		弹栈 6 6的右侧横坐标：7  right[6] = 7 left[6] = 5
		弹栈 5 5的右侧横坐标：7  right[5] = 7 left[5] = 4
		弹栈 2 2的右侧横坐标：7  right[2] = 7 left[2] = 0 
	*/
	/*
	归纳
		right[1] = 2 left[1] = 0  (2-0 -1)*2 2
		right[2] = 7 left[2] = 0  (7-0 -1)*1 6
		right[3] = 5 left[3] = 2  (5-2 -1)*5 10
		right[4] = 5 left[4] = 3  (5-3 -1)*6 6
		right[5] = 7 left[5] = 2  (7-2 -1)*2 8
		right[6] = 7 left[6] = 5  (7-5 -1)*3 3
	*/
	// 未优化版本
	int largestRectangleArea1(vector<int>& heights){
		int n = heights.size();
        heights.insert(heights.begin(), 0);
		heights.push_back(0);
		vector<int> st; // 栈
		st.push_back(0);
		int right[n + 1];
		int left[n + 1];
		
		for(int i = 1; i <= n + 1; i++){
			if(heights[st.back()] <= heights[i]){
				st.push_back(i);
			} else {
				while(heights[i] < heights[st.back()]){
					int back = st.back();
					st.pop_back();
					right[back] = i;
					left[back] = st.back();
				}
				st.push_back(i);
			}
		}
		int maxS = 0;
		for(int i = 1; i <= n; i++){
			if(heights[i]*(right[i]-left[i]-1) > maxS){
				maxS = heights[i]*(right[i]-left[i]-1);
			}
		}
		return maxS;
	}
	
	// 优化后代码
	int largestRectangleArea2(vector<int>& heights) {
		int n = heights.size();
        heights.insert(heights.begin(), 0);
		heights.push_back(0);
		vector<int> st; // 栈
		st.push_back(0);
		
		int maxS = 0;
		for(int i = 1; i <= n + 1; i++){
			if(heights[st.back()] > heights[i]){
				while(heights[i] < heights[st.back()]){
					int back = st.back();
					st.pop_back();
					maxS = max((i - st.back() - 1) * heights[back], maxS);
				}
			}
			st.push_back(i);
		}

		return maxS;
	}
};

int main(){	
	vector<int> a{2,1,5,6,2,3};
	Solution so;
	int res = so.largestRectangleArea1(a);
	cout << "square:" << res << endl;
	return 0;
}